﻿/**************************************************************
 * Copyright gt1987. All rights reserved.
 * 
 * Author: guitao(guitao@eastmoney.com) 
 * Create Date: 2020/9/6 15:01:00
 * Description: TreeNodeAlgorithms
 *          
 * Revision History:
 *      Date         Author               Description
 *              
***************************************************************/

using System;
using System.Collections.Generic;
using System.Text;

namespace Algorithm.Samples
{
    public class TreeNodeAlgorithm_Test
    {

    }

    /// <summary>
    /// 二叉树 算法
    /// 
    /// 1.写递归算法的关键是要明确函数的「定义」是什么，然后相信这个定义，利用这个定义推导最终结果，绝不要跳入递归的细节
    /// </summary>
    public class TreeNodeAlgorithms
    {
        /// <summary>
        /// 给定一个二叉树，返回其节点值自底向上的层次遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）
        /// 给定二叉树 [3,9,20,null,null,15,7],
        /// 返回 [[15,7],[9,20],[3]]
        /// </summary>
        /// <param name="root"></param>
        /// <returns></returns>
        public IList<IList<int>> LevelOrderBottom(TreeNode root)
        {
            IList<IList<int>> result = new List<IList<int>>();
            if (root == null)
            {
                return result;
            }
            Queue<TreeNode> q = new Queue<TreeNode>();
            q.Enqueue(root);
            while (q.Count != 0)
            {
                IList<int> temp = new List<int>();
                int size = q.Count;
                //每层node可以确认最大数量
                //读完node，把子node加入queue中
                for (int i = 0; i < size; i++)
                {
                    var node = q.Dequeue();
                    if (node != null)
                    {
                        temp.Add(node.val);
                        TreeNode left = node.left;
                        TreeNode right = node.right;
                        if (left != null)
                        {
                            q.Enqueue(left);
                        }
                        if (right != null)
                        {
                            q.Enqueue(right);
                        }
                    }
                }
                result.Insert(0, temp);
            }

            return result;
        }
        /// <summary>
        /// 左右 翻转 二叉树
        /// </summary>
        /// <param name="node"></param>
        /// <returns></returns>
        public TreeNode InvertTree(TreeNode root)
        {
            if (root == null) return null;
            TreeNode temp = root.left;
            root.left = root.right;
            root.right = temp;

            InvertTree(root.left);
            InvertTree(root.right);

            return root;
        }
        /// <summary>
        /// 以 root 为根的二叉树就会被拉平为一条链表。
        /// 1、将 root 的左子树和右子树拉平。
        /// 2、将 root 的右子树接到左子树下方，然后将整个左子树作为右子树。
        /// </summary>
        /// <param name="root"></param>
        public void Flatten(TreeNode root)
        {
            if (root == null) return;
            Flatten(root.left);
            Flatten(root.right);

            /**** 后序遍历位置 ****/
            // 1、左右子树已经被拉平成一条链表
            TreeNode left = root.left;
            TreeNode right = root.right;

            // 2、将左子树作为右子树
            root.left = null;
            root.right = left;

            // 3、将原先的右子树接到当前右子树的末端
            TreeNode p = root;
            while (p.right != null)
            {
                p = p.right;
            }
            p.right = right;
        }
    }

    public class TreeNode
    {
        public int val;
        public TreeNode left;
        public TreeNode right;
        public TreeNode(int x) { val = x; }
    }
}
